Answer: That is a deep one.

According to historian Willi Apel, Boethius (c. 480-524) was the first to describe a letter-name system using the Roman alphabet to identify musical notes, and though he used far more than just A-G he did of course start with A. He was not thinking in terms of our modern scales, but of the entire range of pitches found in his list of possible notes. "A" was nothing more than a label for the lowest one.

And that lowest pitch was not necessarily the one we would call A today. Apel says that in two versions of Boethius' system the letter A actually refers to what we now call C. And Notker Babulus (died around 912, taking his wonderful name with him) also used the letter A to refer to what we now call C, which suggests that our modern major scale was already being born - there were no "black keys" at first, and starting on C makes the major scale. But in the end "A" remained where Boethius first had it; as a note that formed the first in a pattern of whole step, half step, whole step, just as now.

Unlike our modern practice, Boethius used different letters for what we would call identical pitch classes in different octaves - the pitch an octave higher than A was not another A; it was O, or H, depending on which of his complicated systems you look at.

Odo of Cluny (c. 878- 942), and later Guido of Arrezzo (c. 995-1050), limited the letters to just A through G and used the same letters for higher pitches of the same octave. Guido also created the system of solfege syllables used as a way of remembering the pattern of whole and half steps. He took the syllables from the words of a well-known Latin hymn, Ut Queant Laxis , each line of which begins on the next higher pitch, starting with C. His audience was familiar with the tune, so it could be used to remember that E-F is a small step, C-D a large one, etc.

(C, Ut) Ut queant laxis
(D, Re) resonare fibris,
(E, Mi) Mira gestorum
(F, Fa) famuli tuorum,
(G, Sol) Solve polluti
(A, La) labii reatum,
Sancte Iohannes.

"Ut" was later changed to Do (who wants to sing "Ut?" What could Julie Andrews do with that?) and that is why the solfege syllables start on C - because Ut Queant Laxis starts on C. The hymn doesn't include B, and Guido wasn't thinking of modern 7-note scales, but when the seventh note was finally added it was given the syllable Si anyway, standing for "Sancte Iohannes" in the original hymn. In English-speaking countries "Si" is now usually sung as "Ti" (hence Ti, I drink with jam and bread).

So, Do-Re-Mi-Fa-Sol-La-Ti began by representing C, D, E, F, G, A, the first 6 notes of what eventually turned into the major scale. In "Moveable Do" solfege we use those to represent the pattern of steps of the major scale starting on any pitch, though some countries continue to use "Fixed Do" solfege, in which the syllables are tied to C, D, E... just as they were 1000 years ago.

Short version: Do-Re-Mi begins on C because that's where Ut Queant Laxis begins, and perhaps the fact that Ut Queant Laxis begins on C also suggests that the major scale was already getting started way back in the first millennium. But Do does not correspond to the note A because "A" originally just referred to the lowest pitch available.